//https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=182&tqId=34762&ru=/exam/oj
// 解决：1.找到链表的中间位置；2.反转后半部链表 ；3.逐个比较元素值；
// comments：good
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class PalindromeList {
  public:
    bool chkPalindrome(ListNode* A) {
        bool res = true;
        if(A==nullptr || A->next == nullptr) return res;
        ListNode* slow_n1 = A;
        ListNode* fast_n2 = A;
        while(fast_n2->next!=nullptr && fast_n2->next->next!=nullptr) {
            slow_n1 = slow_n1->next;
            fast_n2 = fast_n2->next->next;
        }
        ListNode* mid = slow_n1;
        ListNode* tail = ReverseList(mid);
        ListNode* reverse_head = tail;
        while(tail!= nullptr && A!=nullptr) {
            if(tail->val != A->val) {
                res = false;
                break;
            }
            tail = tail->next;
            A = A->next;
        }
        ReverseList(reverse_head);
        return res; 
    }
    ListNode* ReverseList(ListNode* pHead) {
        //反转链表
        if (pHead == nullptr) return nullptr;

        ListNode* cur = pHead;
        ListNode* pre = nullptr;
        ListNode* next = cur->next;

        while (cur != nullptr) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        };
        return pre;
    }
};